package 中等.贪心思想;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一
 * 组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 * <p>
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一
 * 个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；
 * 否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/hand-of-straights
 */
public class 一手顺子_846 {

    public static void main(String[] args) {

        int[] nums = {2, 1};
        System.out.println(isNStraightHand(nums, 2));

    }

    /**
     * 贪心思想
     * 分组之后的第一张牌永远的最小的，先找到数组中最小的元素，它一定是某个分组的开头
     * 当第一组分组成功后，第一组中出现的元素数量-1
     * 找到剩下元素的最小元素
     * 当第二组分组成功后，...
     * ...
     *
     * @param hand
     * @param groupSize
     * @return
     */
    public static boolean isNStraightHand(int[] hand, int groupSize) {
        int length = hand.length;
        if (length % groupSize != 0) {  //牌不能分组
            return false;
        }
        if (groupSize == 1 || groupSize == 0) {  //分组是一张，一定能分
            return true;
        }
        Arrays.sort(hand);  //先排序，可以从小到大去寻找组员
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {  //记录某个元素出现的次数
            map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);
        }
        for (int i = 0; i < length; i++) {  //类似优先队列，从小到大依次出队列
            int cur = hand[i];
            if (map.getOrDefault(cur, 0) == 0) {  //当前元素已经被分组
                continue;
            }
            map.put(cur, map.get(cur) - 1);  //分组头元素数量-1
            for (int j = 1; j < groupSize; j++) {  //cur头元素已经存在，所以新增groupSize-1个元素
                if (map.getOrDefault(cur + j, 0) <= 0) {  //没有符合条件的元素来分组
                    return false;
                }
                map.put(cur + j, map.get(cur + j) - 1);  //被分组的元素数量-1
            }
        }
        return true;
    }

}
